/**
 * Created by Administrator on 2017/8/10.
 题目：春节期间小明使用微信收到很多个红包，非常开心。
 在查看领取红包记录时发现，某个红包金额出现的次数超过了红包总数的一半。
 请帮小明找到该红包金额。写出具体算法思路和代码实现，要求算法尽可能高效。
 给定一个红包的金额数组gifts及它的大小n，请返回所求红包的金额。
 没找到，返回0。

 */
public class redPocket {
    private static int count;
    private static float curMoney;

    //两个不同的就直接消，只能在确保存在的情况下用...（或加以验证）
    //不过这个思路很好
    //排序以后取中位数也是
    public static float algorithm1(float[] money){
        int index = money.length;
        curMoney = money[0];
        count = 1;
        for(int i = 1; i < index; i++){
            if(money[i] == curMoney){
                count++;
            }else count--;
            if(count == 0){
                curMoney = money[i];
                count = 1;
            }
        }
        return curMoney;
    }

    public static float algorithm1_cont(float[] money){
        int index = money.length;
        float candidate = algorithm1(money);
        int mCount = 0;
        for(int i = 0; i < index; i++){
            if(money[i] == candidate){ mCount++; }
        }
        if(mCount >= index/2){return candidate;}
        else return 0;
    }

    public static void main(String[] args) {
        float[] gifts = {1.1f,3.0f,2.0f,1.1f};
        System.out.println(algorithm1_cont(gifts));
    }
}
